{\magonebf 3.1 One Dimensional Arrays (array)}

\decl array E 

{\bf 1. Definition}

An instance $A$ of the parameterized data type \name\ is a mapping from 
an interval $I =[a..b]$ of integers, called the index set of $A$, to the set of 
variables of data type $E$, called the element type of $A$. $A(i)$ 
is called the element at position $i$. 


\bigskip
{\bf 2. Creation}

\create A (int\ a,\ int\ b)

creates an instance \var\ of type \name\ with index set $[a..b]$.


\bigskip
{\bf 3. Operations}
\cleartabs
\+&\hskip 1.5truecm &\hskip 6truecm &\cr
\+\opa E\&   {int\ i}                     
                                     {returns $A(i)$. \precond $a\le i\le b$  }
\smallskip
\+\op  int   low {}                  
                                     {returns the minimal index $a$}
\smallskip
\+\op  int   high {}                 
                                     {returns the maximal index $b$}
\smallskip
\+\op  void  sort {int\ (*cmp)(E\&, E\&)} 
                     {sorts the elements of \var, using function $cmp$}
\+\nop               {to compare two elements, i.e., if $(in_a,\dots,in_b)$}
\+\nop               {and $(out_a,\dots,out_b)$ denote the values of the}
\+\nop               {variables $(A(a),\dots,A(b))$ before and after the}
\+\nop               {call of sort, then $cmp(out_i,out_j) \le 0$ for $i\le j$}
\+\nop               {and there is a permutation $\pi$ of $[a..b]$ such that}
\+\nop               {$out_i=in_{\pi(i)}$ for $a \le i \le b$.}
\smallskip
\+\op  void  sort {int\ (*cmp)(E\&, E\&),\ int\ l,\ int\ h}  {}
\+\nop               {applies the above defined sorting operations to}
\+\nop               {the sub-array \var$[l..h]$.}
\smallskip
\+\op  int   binary\_search {E\ x,\ int\ (*cmp)(E\&, E\&)}  {}
\+\nop               {performs a binary search for $x$. Returns $i$}
\+\nop               {with $A[i] = x$ if $x$ in $A$, $A$.low$()-1$}
\+\nop               {otherwise. Function $cmp$ is used to compare}
\+\nop               {two elements. \precond $A$ must be sorted}
\+\nop               {according to $cmp$.}
\medskip
\+\op void       read {istream\ I}
                     {reads $b-a+1$ objects of type $E$ from the}
\+\nop               {input stream $I$ into the array $A$ using the}
\+\nop               {overloaded $Read$ function (cf.~section 1.5)}
\smallskip
\+\op void       read {}
                     {Calls $A$.read($cin$) to read $A$ from the}
\+\nop               {standard input stream $cin$.}
\smallskip
\+\op void       read {string\ s}
                     {As above, uses string $s$ as a prompt.}
\medskip
\+\op void       print {ostream\ O,\ char\ space =\ '\ '}    {} 
\+\nop               {Prints the contents of array $A$ to the output}
\+\nop               {stream $O$ using the overload $Print$ function}
\+\nop               {(cf.~section 1.5) to print each element. The}
\+\nop               {elements are separated by the character $space$.}
\smallskip
\+\op void       print {char\ space =\ '\ '}
                     {Calls $A$.print($cout$, $space$) to print $A$ on}
\+\nop               {the standard output stream $cout$.}
\smallskip
\+\op void       print {string\ s,\ char\ space =\ '\ '}    {} 
\+\nop               {As above, uses string $s$ as a header.}


\bigskip
{\bf 4. Implementation}

Arrays are implemented by \CC vectors. The access operation takes time
$O(1)$, the sorting is realized by quicksort (time $O(n \log n)$) and
the binary\_search operation takes time $O(\log n)$, where $n = b-a+1$.
The space requirement is $O(|I|)$.

